<?xml version="1.0" encoding="ISO-8859-1"?>
<metadatalist>
	<metadata ReferenceType="Conference Proceedings">
		<site>sibgrapi.sid.inpe.br 802</site>
		<holdercode>{ibi 8JMKD3MGPEW34M/46T9EHH}</holdercode>
		<identifier>6qtX3pFwXQZG2LgkFdY/QGG9a</identifier>
		<repository>sid.inpe.br/sibgrapi@80/2007/07.09.17.59</repository>
		<lastupdate>2007:07.09.17.59.09 sid.inpe.br/banon/2001/03.30.15.38 administrator</lastupdate>
		<metadatarepository>sid.inpe.br/sibgrapi@80/2007/07.09.17.59.10</metadatarepository>
		<metadatalastupdate>2022:06.14.00.13.27 sid.inpe.br/banon/2001/03.30.15.38 administrator {D 2007}</metadatalastupdate>
		<doi>10.1109/SIBGRAPI.2007.15</doi>
		<citationkey>CoutoSouzReze:2007:ExEfAl</citationkey>
		<title>An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem</title>
		<format>Printed, On-line.</format>
		<year>2007</year>
		<numberoffiles>1</numberoffiles>
		<size>210 KiB</size>
		<author>Couto, Marcelo C.,</author>
		<author>Souza, Cid C. de,</author>
		<author>Rezende, Pedro J. de,</author>
		<affiliation>Institute of Computing, State University of Campinas, Campinas - Brazil</affiliation>
		<affiliation>Institute of Computing, State University of Campinas, Campinas - Brazil</affiliation>
		<affiliation>Institute of Computing, State University of Campinas, Campinas - Brazil</affiliation>
		<editor>Falcão, Alexandre Xavier,</editor>
		<editor>Lopes, Hélio Côrtes Vieira,</editor>
		<conferencename>Brazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI)</conferencename>
		<conferencelocation>Belo Horizonte, MG, Brazil</conferencelocation>
		<date>7-10 Oct. 2007</date>
		<publisher>IEEE Computer Society</publisher>
		<publisheraddress>Los Alamitos</publisheraddress>
		<booktitle>Proceedings</booktitle>
		<tertiarytype>Full Paper</tertiarytype>
		<transferableflag>1</transferableflag>
		<versiontype>finaldraft</versiontype>
		<keywords>Art Gallery, Exact Solution, Orthogonal Polygons, Integer Programming, Set Covering.</keywords>
		<abstract>In this paper, we propose an exact algorithm to solve the Orthogonal Art Gallery problem in which guards can only be placed on the vertices of the polygon $ P$ representing the gallery. Our approach is based on a discretization of $ P$ into a finite set of points in its interior. The algorithm repeatedly solves an instance of the Set Cover problem obtaining a minimum set $ Z$ of vertices of $ P$ that can view all points in the current discretization. Whenever $ P$ is completely visible from $ Z$ , the algorithm halts; otherwise, the discretization is refined and another iteration takes place. We establish that the algorithm always converges to an optimal solution by presenting a worst case analysis of the number of iterations that could be effected. Even though these could theoretically reach $ O(n^4)$ , our computational experiments reveal that, in practice, they are linear in $ n$ and, for $ n\leq 200$ , they actually remain less than three in almost all instances. Furthermore, the low number of points in the initial discretization, $ O(n^2)$ , compared to the possible $ O(n^4)$ atomic visibility polygons, renders much shorter total execution times. Optimal solutions found for different classes of instances of polygons with up to 200 vertices are also described.</abstract>
		<language>en</language>
		<targetfile>couto-ArtGallery.pdf</targetfile>
		<usergroup>cid@ic.unicamp.br administrator</usergroup>
		<visibility>shown</visibility>
		<nexthigherunit>8JMKD3MGPEW34M/46SF8Q5</nexthigherunit>
		<nexthigherunit>8JMKD3MGPEW34M/4742MCS</nexthigherunit>
		<citingitemlist>sid.inpe.br/sibgrapi/2022/05.14.00.14 3</citingitemlist>
		<hostcollection>sid.inpe.br/banon/2001/03.30.15.38</hostcollection>
		<lasthostcollection>sid.inpe.br/banon/2001/03.30.15.38</lasthostcollection>
		<url>http://sibgrapi.sid.inpe.br/rep-/sid.inpe.br/sibgrapi@80/2007/07.09.17.59</url>
	</metadata>
</metadatalist>